{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Create Grid World"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(['DOWN', 'LEFT'], [{'x': 4, 'y': 1}, {'x': 3, 'y': 0}])\n",
      "  --- --- --- --- ---\n",
      " | 0 | 0 | 0 | 0 | p |\n",
      "  --- --- --- --- ---\n",
      " | 0 | x | x | x | 0 |\n",
      "  --- --- --- --- ---\n",
      " | 0 | x | 0 | 0 | -1 |\n",
      "  --- --- --- --- ---\n",
      " | 0 | 0 | 0 | 0 | 0 |\n",
      "  --- --- --- --- ---\n"
     ]
    }
   ],
   "source": [
    "class Gridworld:\n",
    "    def __init__(self, height, width, coins=[(0, 4)], ghosts=[(2,4)], walls=[(1,1),(1,2),(1,3),(2,1)]):\n",
    "        self.height = height\n",
    "        self.width = width\n",
    "        \n",
    "        self.walls = walls\n",
    "        self.grid = []\n",
    "        \n",
    "        self.terminal_states = coins + ghosts\n",
    "        \n",
    "        self.pacman = {'x': 4, 'y': 0}\n",
    "        \n",
    "        # create empty array of 0's for grid\n",
    "        for i in range(height):\n",
    "            row = []\n",
    "            for j in range(width):\n",
    "                row.append(0)\n",
    "            \n",
    "            self.grid.append(row)\n",
    "\n",
    "        # Place coins in grid         \n",
    "        for coin in coins:\n",
    "            self.grid[coin[0]][coin[1]] = 1\n",
    "        \n",
    "        # Place ghosts in grid\n",
    "        for ghost in ghosts:\n",
    "            self.grid[ghost[0]][ghost[1]] = -1\n",
    "        \n",
    "        # Place walls in grid\n",
    "        for wall in walls:\n",
    "            self.grid[wall[0]][wall[1]] = 'x'\n",
    "            \n",
    "    def show(self):\n",
    "        line = \" \"\n",
    "        for i in range(self.width):\n",
    "            line += \" ---\"\n",
    "        \n",
    "        print(line)\n",
    "        for y in range(self.height):    \n",
    "            for x in range(self.width):\n",
    "                print(' | ',end='')\n",
    "                \n",
    "                if (self.pacman['x'] == x and self.pacman['y'] == y):\n",
    "                    print('p',end='')\n",
    "                else:\n",
    "                    print(self.grid[y][x],end='')\n",
    "            print(\" |\")\n",
    "            print(line)\n",
    "    \n",
    "    def available_actions(self):\n",
    "        actions = []\n",
    "        locations = []\n",
    "        \n",
    "        # Check for Up\n",
    "        if self.pacman[\"y\"] - 1 >= 0:\n",
    "            new_loc = {'x': self.pacman[\"x\"], 'y': self.pacman[\"y\"] - 1}\n",
    "                       \n",
    "            if self.grid[new_loc['y']][new_loc['x']] != 'x':\n",
    "                actions.append(\"UP\")\n",
    "                locations.append(new_loc)\n",
    "\n",
    "       # Check for Right        \n",
    "        if self.pacman[\"x\"] + 1 < self.width:\n",
    "            new_loc = {'x': self.pacman[\"x\"] + 1, 'y': self.pacman[\"y\"]}\n",
    "            if self.grid[new_loc['y']][new_loc['x']] != 'x':\n",
    "                actions.append(\"RIGHT\")\n",
    "                locations.append(new_loc)\n",
    "                       \n",
    "        # Check for Down            \n",
    "        if self.pacman[\"y\"] + 1 < self.height:\n",
    "            new_loc = {'x': self.pacman[\"x\"], 'y': self.pacman[\"y\"] + 1 }\n",
    "            if self.grid[new_loc['y']][new_loc['x']] != 'x':\n",
    "                actions.append(\"DOWN\")\n",
    "                locations.append(new_loc)\n",
    "                       \n",
    "        # Check for Left            \n",
    "        if self.pacman[\"x\"] - 1 >= 0:\n",
    "            new_loc = {'x': self.pacman[\"x\"] - 1, 'y': self.pacman[\"y\"]}\n",
    "            if self.grid[new_loc['y']][new_loc['x']] != 'x':\n",
    "                actions.append(\"LEFT\")\n",
    "                locations.append(new_loc)\n",
    "        \n",
    "        return actions, locations\n",
    "        \n",
    "    \n",
    "    def move(self, direction):\n",
    "        \n",
    "        if direction == \"UP\":\n",
    "            new_loc = {'x': self.pacman[\"x\"], 'y': self.pacman[\"y\"] - 1 if self.pacman[\"y\"] - 1 > 0 else 0}\n",
    "            if (self.grid[new_loc['y']][new_loc['x']] != 'x'):\n",
    "                self.pacman = new_loc\n",
    "            \n",
    "        elif direction == \"RIGHT\":\n",
    "            new_loc = {'x': self.pacman[\"x\"] + 1 if self.pacman[\"x\"] + 1 < self.width else self.pacman[\"x\"], 'y': self.pacman[\"y\"]}\n",
    "            if (self.grid[new_loc['y']][new_loc['x']] != 'x'):\n",
    "                self.pacman = new_loc\n",
    "            \n",
    "        elif direction == \"DOWN\":\n",
    "            new_loc = {'x': self.pacman[\"x\"], 'y': self.pacman[\"y\"] + 1 if self.pacman[\"y\"] + 1 < self.height else self.pacman[\"y\"] }\n",
    "            if (self.grid[new_loc['y']][new_loc['x']] != 'x'):\n",
    "                self.pacman = new_loc\n",
    "            \n",
    "        elif direction == \"LEFT\":\n",
    "            new_loc = {'x': self.pacman[\"x\"] - 1 if self.pacman[\"x\"] - 1 > 0 else 0, 'y': self.pacman[\"y\"]}\n",
    "            if (self.grid[new_loc['y']][new_loc['x']] != 'x'):\n",
    "                self.pacman = new_loc\n",
    "            \n",
    "        else:\n",
    "            print(\"Cannot find movement.\")\n",
    "        \n",
    "        done = False\n",
    "        if (self.grid[self.pacman['y']][self.pacman['x']] != 0):\n",
    "            done = True\n",
    "        \n",
    "        return self.grid[self.pacman['y']][self.pacman['x']], done\n",
    "    \n",
    "\n",
    "g = Gridworld(4, 5)\n",
    "print(g.available_actions())\n",
    "g.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Formulate Bellman Equation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Bellman equation is defined as follows:\n",
    "\n",
    "\\begin{equation*}\n",
    "V(s) = max_a ( R(s, a) + \\gamma V(s')\n",
    "\\end{equation*}\n",
    "\n",
    "- V = Value\n",
    "- S = current state\n",
    "- a = Action\n",
    "- R = Reward\n",
    "- gamma = discount factor\n",
    "- s' = prime means next state\n",
    "\n",
    "Completley detrministicly - the actions we take happen 100% of the time.\n",
    "\n",
    "### Gamma\n",
    "If gamma is equal to one, every square is going to have a value of one... make this into some sort of question and then an exercise to work this out.\n",
    "\n",
    "Higher number = long term thinking."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "height = 4\n",
    "width = 5\n",
    "actions = 4\n",
    "gamma = 0.9\n",
    "\n",
    "policy =[]\n",
    "for i in range(height):\n",
    "    row = []\n",
    "    for j in range(width):\n",
    "        row.append('x')\n",
    "\n",
    "    policy.append(row)\n",
    "\n",
    "g = Gridworld(4, 5)\n",
    "\n",
    "\n",
    "# Starting at the end location work backwards to populate policy\n",
    "def calculate_value_for_location(y, x, start=False):\n",
    "#     print(\"---\")\n",
    "#     print(str(x) + \", \" + str(y))\n",
    "\n",
    "    g.pacman = {'x': x, 'y': y}\n",
    "#     g.show()\n",
    "    available_actions, available_locations = g.available_actions()\n",
    "    reward_for_current_location  = g.grid[y][x]\n",
    "    \n",
    "#     print(\"Available actions: \" + str(available_actions))\n",
    "    \n",
    "    if (policy[y][x] != 'x'):\n",
    "#         print(\"Already done... exiting\")\n",
    "        return\n",
    "        \n",
    "        \n",
    "\n",
    "    for terminal_state in g.terminal_states:\n",
    "        if (y == terminal_state[0] and x == terminal_state[1]):\n",
    "            policy[y][x] = reward_for_current_location\n",
    "            if(start == False):\n",
    "                return\n",
    "\n",
    "    value_of_available_locations = [policy[loc['y']][loc['x']] if policy[loc['y']][loc['x']] != 'x' else 0 for loc in available_locations]\n",
    "#     print(value_of_available_locations)\n",
    "    reward_for_current_location  = g.grid[y][x]\n",
    "    reward_for_current_location = reward_for_current_location + gamma * max(value_of_available_locations)\n",
    "\n",
    "    policy[y][x] = round(reward_for_current_location, 2)\n",
    "#     print(policy)\n",
    "#     print(available_actions)\n",
    "\n",
    "    for loc, action in zip(available_locations, available_actions):\n",
    "#         print(\"Action taken: \" + str(action))\n",
    "#         print(\"location: \" + str(loc))\n",
    "#         input()\n",
    "        calculate_value_for_location(y=loc['y'], x=loc['x'])\n",
    "        \n",
    "        \n",
    "calculate_value_for_location(0,4, start=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0.66, 0.73, 0.81, 0.9, 1.0],\n",
       " [0.59, 'x', 'x', 'x', 0.9],\n",
       " [0.53, 'x', 0.35, 0.32, -1],\n",
       " [0.48, 0.43, 0.39, 0.35, 0.32]]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "policy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A problem occures when there is non-deterministic environment. To know the value of the current state you need to knwo the valye of the next statem and to knwo the next state you need to know the previous state, and so on. Need a new method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
